A fully homomorphic encryption algorithm includes an algorithm for generating a public key, a private key, and a computation key, an encryption algorithm, a decryption algorithm, and a ciphertext computation function. The fully homomorphic encryption algorithm is mainly used to authenticate a computation result of distributed computation, that is, a technology for authenticating a fully homomorphic message.
Currently, a specific implementation manner of the technology for authenticating a fully homomorphic message is as follows: A terminal acquires a message authentication key, where the message authentication key includes a public key, a private key, and a computation key that are acquired according to the foregoing fully homomorphic encryption algorithm, and further includes a first character string and a second character string. The first character string is a subset of a randomly-generated set {1, 2, . . . , n−1, n} and has a length of n/2, and the second character string is a random character string that consists of 0 and 1 and has a length of n, where n is an integer greater than or equal to 2. The terminal generates an authentication fingerprint of each bit of to-be-computed data according to the message authentication key and the encryption algorithm in the foregoing fully homomorphic encryption algorithm, and sends the to-be-computed data, the authentication fingerprint, the message authentication key, and the foregoing fully homomorphic encryption algorithm together to a server. The server computes the to-be-computed data according to a pre-configured computation function used to compute the to-be-computed data to acquire a computation result, computes a first component of an authentication fingerprint of the computation result by using a pre-configured family of hash functions, computes each character of the first character string in the message authentication key according to the computation result, the authentication fingerprint of each bit of the to-be-computed data, and the foregoing computation key, and by using the ciphertext computation function in the foregoing fully homomorphic encryption algorithm, to acquire a second component of the authentication fingerprint of the computation result, to finally acquire an entire authentication fingerprint of the computation result, and returns the computation result and the authentication fingerprint of the computation result to the terminal. The terminal first recomputes a first component of the authentication fingerprint of the computation result according to the pre-configured family of hash functions to determine that the first component of the authentication fingerprint of the computation result that is obtained by means of recomputation is the same as the first component of the authentication fingerprint that is returned by the server; and then performs further authentication, for the jth bit of the to-be-computed data and the ith character of the first character string of the terminal, generates a pseudo random string rand (i, j) according to a pre-configured pseudo random function, inputs 0 and the rand (i, j) into the foregoing encryption algorithm to acquire an encryption ciphertext corresponding to 0 in the pseudo random string rand (i, j), performs computation according to the encryption ciphertext, the pre-configured computation function used to compute the to-be-computed data, and the computation key, and by using the ciphertext computation function in the fully homomorphic encryption algorithm, to acquire the ith second component of the authentication fingerprint of the computation result, performs n/2 times of such computation according to the foregoing method to acquire all second components of the authentication fingerprint of the computation result, and determines, by means of comparison, whether the second component of the authentication fingerprint of the computation result that is sent by the server are the same as the second components of the authentication fingerprint of the computation result that are acquired by the terminal. If the authentication fingerprint of the computation result that is sent by the server is the same as the authentication fingerprint of the computation result that is obtained by the terminal by means of recomputation, it is determined that the computation result is correct. A computation result of each bit of the to-be-computed data is verified according to the foregoing method.
However, because the first character string in the message authentication key consists of a subset of {1, 2, . . . , n−1, n} and has a length of n/2, computation of the authentication fingerprint of each bit of the to-be-computed data is complex. In addition, when an authentication server of the terminal returns the computation result, it is required to obtain the computation result by means of recomputation, and to perform n/2 times of computation on each bit of the to-be-computed data to acquire the second component of the authentication fingerprint corresponding to the computation result, to compare the second component of the authentication fingerprint corresponding to the computation result with a second component of a second authentication fingerprint for authentication. Therefore, an amount of computation is large and verification efficiency is low.